1. Field of the Invention
This invention relates in general to data processing, and more particularly to faster transforms that use multiple scaled terms.
2. Description of Related Art
Transforms, which take data from one domain (e.g., sampled data) to another (e.g., frequency space), are used in many signal and/or image processing applications. Such transforms are used for a variety of applications, including, but not limited to data analysis, feature identification and/or extraction, signal correlation, data compression, or data embedding. Many of these transforms require efficient implementation for real-time and/or fast execution whether or not compression is used as part of the data processing.
Data compression is desirable in many data handling processes, where too much data is present for practical applications using the data. Commonly, compression is used in communication links, to reduce transmission time or required bandwidth. Similarly, compression is preferred in image storage systems, including digital printers and copiers, where xe2x80x9cpagesxe2x80x9d of a document to be printed may be stored temporarily in memory. Here the amount of media space on which the image data is stored can be substantially reduced with compression. Generally speaking, scanned images, i.e., electronic representations of hard copy documents, are often large, and thus make desirable candidates for compression.
In data processing, data is typically represented as a sampled discrete function. The discrete representation is either made deterministically or statistically. In a deterministic representation, the point properties of the data are considered, whereas, in a statistical representation, the average properties of the data are specified. In particular examples referred to herein, the terms images and image processing will be used. However, those skilled in the art will recognize that the present invention is not meant to be limited to processing images but is applicable to processing different data, such as audio data, scientific data, image data, etc.
In a digital image processing system, digital image signals are formed by first dividing a two-dimensional image into a grid. Each picture element, or pixel, in the grid has associated therewith a number of visual characteristics, such as brightness and color. These characteristics are converted into numeric form. The digital image signal is then formed by assembling the numbers associated with each pixel in the image into a sequence which can be interpreted by a receiver of the digital image signal.
Signal and image processing frequently require converting the input data into transform coefficients for the purposes of analysis. Often only a quantized version of the coefficients is needed (e.g. JPEG/MPEG data compression or audio/voice compression). Many such applications need to be done fast in real time such as the generation of JPEG data for high speed printers.
Pressure is on the data signal processing industry to find the fastest method by which to most effectively and quickly perform the digital signal processing. As in the field of compression generally, research is highly active and competitive in the field of fast transform implementation. Researchers have made a wide variety of attempts to exploit the strengths of the hardware intended to implement the transforms by exploiting properties found in the transform and inverse transform.
One such technique is the ISO 10918-1 JPEG International Standard /ITU-T Recommendation T.81. The draft JPEG standard is reproduced in Pennebaker and Mitchell, JPEG: Still Image Data Compression Standard, New York, Van Nostrand Reinhold, 1993, incorporated herein by reference. One compression method defined in the JPEG standard, as well as other emerging compression standards, is discrete cosine transform (DCT) coding. Images compressed using DCT coding are decompressed using an inverse transform known as the inverse DCT (IDCT). An excellent general reference on DCTs is Rao and Yip, Discrete Cosine Transform, New York, Academic Press, 1990, incorporated herein by reference. It will be assumed that those of ordinary skill in this art are familiar with the contents of the above-referenced books.
It is readily apparent that if still images present storage problems for computer users and others, motion picture storage problems are far more severe, because full-motion video may require up to 60 images for each second of displayed motion pictures. Therefore, motion picture compression techniques have been the subject of yet further development and standardization activity. Two important standards are ISO 11172 MPEG International Standard and ITU-T Recommendation H.261. Both of these standards rely in part on DCT coding and IDCT decoding.
However, research generally focuses on specific techniques, such as the above-mentioned techniques that used DCT coding to provide the desired degree of compression. Nevertheless, other transforms may be used to provide certain advantages under certain circumstances. For example, in the DCT compression coding method discussed above, an input image is divided into many uniform blocks and the two-dimensional discrete cosine transform function is applied to each block to transform the data samples into a set of transform coefficients to remove the spatial redundancy. However, even though a high compression rate may be attained, a blocking effect, which may be subtle or obvious, is generated. Further, vector quantization methods that may be utilized by the compression system are advantageous due to their contribution to the high compression rate. On the other hand, a sub-band method may reduce the blocking effect which occurs during high rates of data compression. The wavelet transform (WT) or Sub-Band Coding (SBC) methods encode signals based on, for example, time and frequency components. As such, these transform methods can be useful for analyzing non-stationary signals and have the advantage that they may be designed to take into account the characteristics of the human visual system (HVS) for image analysis.
It can be seen then that there is a need to provide a method and apparatus that provides faster transform calculations, decreased software execution times and reduced hardware requirements.
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses fast transforms that use multiple scaled terms.
The present invention solves the above-described problems by splitting discrete transforms into sub-transforms that are independently calculated using scaled terms on the transform constants. Further, optimal representations of the scaled terms for binary arithmetic are found. The resulting calculations result in fast transform calculations, decreased software execution times and reduced hardware requirements. Moreover, those skilled in the art will recognize that the inverse transform can often be implemented using the same method so that, in general, the same number of operations is used.
A method in accordance with the principles of the present invention includes arranging transform equations into at least one collection having at least two transform constants and independently scaling the at least two transform constants for each collection with a scaling term to maintain a substantially uniform ratio between the at least two transform constants within the at least one collection.
Other embodiments of a method in accordance with the principles of the invention may include alternative or optional additional aspects. One such aspect of the present invention is that the method further includes separating data into at least one block and transforming the block into transform data via the scaled transform equations.
Another aspect of the present invention is that the scaling term is chosen according to a predetermined cost function.
Another aspect of the present invention is that the predetermined cost function comprises selecting the scaling term so that the largest error on any transform coefficient is no larger than a predetermined error percentage.
Another aspect of the present invention is that the predetermined cost function comprises selecting the scaling term so that the largest error on each involved transform coefficient is no larger than its individual predetermined error percentage.
Another aspect of the present invention is that the predetermined cost function comprises selecting the scaling term so that predetermined transform constants have an error less than or equal to a predetermined error percentage.
Another aspect of the present invention is that the predetermined cost function comprises selecting the scaling term so that each involved predetermined transform constant has an error less than or equal to its individual predetermined error percentage.
Another aspect of the present invention is that the predetermined cost function comprises selecting the scaling term and representations for the transform constants so that all transform constants for a collection possess simultaneous binary representations with predetermined characteristics.
Another aspect of the present invention is that the predetermined characteristics comprise a minimum number of common power-of-2 terms.
Another aspect of the present invention is that the selecting of the scaling term and representations for the transform constants so that all transform constants for a collection possess simultaneous binary representations with a minimum number of common power-of-2 terms is implemented when binary arithmetic shifts may be more efficient than multiplication operations.
Another aspect of the present invention is that the predetermined characteristics comprise a maximized clustering of non-zero power-of-2 terms.
Another aspect of the present invention is that the selecting of the scaling term so that all transform constants for a collection possess simultaneous binary representations with a maximized clustering of non-zero power-of-2 terms is implemented when multiplication operations employing smaller integers are more desirable than multiplies employing larger numbers.
Another aspect of the present invention is that whether the coefficient in a power-of-2 polynomial representing the constant is non-zero is tracked.
Another aspect of the present invention is that a value of the bit position determines the power-of-2 term.
Another aspect of the present invention is that maximizing the clustering of non-zero power-of-2 terms includes finding all representations of the scaled constants by a) setting a first variable to an ith element in the block, b) initializing a second variable to a value of 2, c) initializing a bitmask to binary 3, d) analyzing the bits to determine whether the ith element indicated by the first variable is a candidate representation for doing the term reordering using 2n+2nxe2x88x921=2n+1xe2x88x922nxe2x88x921, e) encoding the ith element by adding the second variable to the first variable to perform an effective power-of-2 change given by 2n+2nxe2x88x921=2n+1xe2x88x922nxe2x88x921, f) obtaining a new representation and incrementing the first variable to the i+1th element, g) shifting the mask and second variable left one bit and h) repeating d-g.
Another aspect of the present invention is that the method further includes shifting the mask left after checking if the first variable matching the mask bits were set thereby putting a zero at the right and increasing the power of 2 that is used for reordering in 2n+2nxe2x88x921=2n+1xe2x88x922nxe2x88x921.
Another aspect of the present invention is that the collections represent disjoint sets of transform equations of partial calculations.
Another aspect of the present invention is that the collections do not represent disjoint sets of transform equations of partial calculations.
Another aspect of the present invention is that the method further includes selecting an independent scaling term for the transform constants in each of the at least one collections.
In another embodiment of the present invention, a data compression system is provided. The data compression system includes a transformer for applying a linear transform to decorrelate data into transform coefficients using transform equations, the transform equations being formed by arranging transform equations into at least one collection having at least two transform constants and independently scaling the at least two transform constants for each collection with a scaling term to maintain a substantially uniform ratio between the at least two transform constants within the at least one collection, wherein the scaling term is chosen according to a predetermined cost function and a quantizer for quantizing the transformed data into quantized data by reducing a number of bits needed to represent the transform coefficients.
In another embodiment of the present invention, a printer is provided. The printer includes memory for storing image data, a processor for processing the image data to provide a compressed print stream output and a printhead driving circuit for controlling a printhead to generate a printout of the image data, wherein the processor applies a linear transform to decorrelate data into transform coefficients using transform equations, the transform equations being formed by arranging transform equations into at least one collection having at least two transform constants and independently scaling the at least two transform constants for each collection with a scaling term to maintain a substantially uniform ratio between the at least two transform constants within the at least one collection, wherein the scaling term is chosen according to a predetermined cost function
In another embodiment of the present invention, an article of manufacture is provided. The article of manufacture includes a program storage medium readable by a computer, the medium tangibly embodying one or more programs of instructions executable by the computer to perform a method for arranging transform equations into at least one collection having at least two transform constants and independently scaling the at least two transform constants for each collection with a scaling term to maintain a substantially uniform ratio between the at least two transform constants within the at least one collection, wherein the scaling term is chosen according to a predetermined cost function.
In another embodiment of the present invention, a data analysis system is provided. The data analysis system includes transform equations being formed by arranging transform equations into at least one collection having at least two transform constants and independently scaling the at least two transform constants for each collection with a scaling term to maintain a substantially uniform ratio between the at least two transform constants within the at least one collection, wherein the scaling term is chosen according to a predetermined cost function and a transformer for applying the transform equations to perform a linear transform to decorrelate data into transform coefficients.
These and various other advantages and features of novelty which characterize the invention are pointed out with particularity in the claims annexed hereto and form a part hereof. However, for a better understanding of the invention, its advantages, and the objects obtained by its use, reference should be made to the drawings which form a further part hereof, and to accompanying descriptive matter, in which there are illustrated and described specific examples of an apparatus in accordance with the invention.